

# 416. 分割等和子集


# def canPartition(nums):
#     """
#     :type nums: List[int]
#     :rtype: bool
#     """
#     nums.sort()
#     if sum(nums) % 2 != 0:
#         return False
#     wight = sum(nums) / 2
#     temp = []
#     result = [False]
#
#     def backtrack(startIndex):
#         if sum(temp) == wight:
#             result[0] = True
#             return
#         for i in range(startIndex, len(nums)):
#             temp.append(nums[i])
#             backtrack(i + 1)
#             temp.pop()
#
#     backtrack(0)
#     return result[0]


def canPartition(nums):
    if sum(nums) % 2 != 0:
            return False
    wight = sum(nums)//2
    dp = [[None]*(wight+1) for _ in range(0,len(nums))]
    for i in range(0,len(nums)):
        dp[i][0] = 0
    for i in range(0,nums[0]):
        dp[0][i] = 0
    for i in range(nums[0],wight+1):
        dp[0][i] = 1
    for i in range(1,len(nums)):
        for j in range(1,wight+1):
            if j<nums[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])
    print(dp)
    if dp[len(nums)-1][wight] == wight:
        return True
    else:
        return False


if __name__ == "__main__":
    boolean = canPartition([1,5,11,5])
    print(boolean)
